class Solution {
public:

    TreeNode* pre(vector<int>& preorder, vector<int>& inorder, int& i, int begin, int end)
    {
        if (begin > end)
            return nullptr;
        int rooti = 0;
        while (rooti < end)
        {
            if (preorder[i] == inorder[rooti])
            {
                break;
            }
            rooti++;
        }
        TreeNode* node = new TreeNode(preorder[i++]);
        node->left = pre(preorder, inorder, i, begin, rooti - 1);
        node->right = pre(preorder, inorder, i, rooti + 1, end);
        return node;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        TreeNode* root = pre(preorder, inorder, i, 0, inorder.size() - 1);
        return root;
    }
};